﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0040_FloodFill : IAlgorithm
    {
        // 733. 图像渲染

        // 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

        // 给你一个坐标(sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

        // 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点
        // 与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

        // 最后返回经过上色渲染后的图像。

        //注意:
        //   image 和 image[0] 的长度在范围[1, 50] 内。
        //   给出的初始点将满足 0 <= sr<image.length 和 0 <= sc<image[0].length。
        //   image[i][j] 和 newColor 表示的颜色值在范围[0, 65535]内。

        // - - 
        // 其实就是给你一个矩阵：
        // [[1,1,1],
        // [1,1,0],
        // [1,0,1]]

        // 然后给你一个坐标（1,1）和新数值（2），要求你把坐标及其周围的旧数值变为新数值，即新矩阵为：
        // [[2,2,2],
        // [2,2,0],
        // [2,0,1]]

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        int[] dx = { 1, 0, 0, -1 };
        int[] dy = { 0, 1, -1, 0 };
        public int[][] FloodFill(int[][] image, int sr, int sc, int newColor)
        {
            int[] dx = { 1, 0, 0, -1 };
            int[] dy = { 0, 1, -1, 0 };
            int currColor = image[sr][sc];
            if (currColor == newColor)
                return image;
            int n = image.Length, m = image[0].Length;
            Queue<int[]> queue = new Queue<int[]>();
            queue.Enqueue(new int[] { sr, sc });
            image[sr][sc] = newColor;
            while (queue.Count != 0)
            {
                int[] cell = queue.Dequeue();
                int x = cell[0], y = cell[1];
                for (int i = 0; i < 4; i++)
                {
                    int mx = x + dx[i], my = y + dy[i];
                    if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor)
                    {
                        queue.Enqueue(new int[] { mx, my });
                        image[mx][my] = newColor;
                    }
                }
            }
            return image;
        }

        public int[][] FloodFill1(int[][] image, int sr, int sc, int newColor)
        {
            int currColor = image[sr][sc];
            if (currColor != newColor)
            {
                DFS(image, sr, sc, currColor, newColor);
            }
            return image;
        }
        private void DFS(int[][] image, int x, int y, int color, int newColor)
        {
            if (image[x][y] == color)
            {
                image[x][y] = newColor;
                for (int i = 0; i < 4; i++)
                {
                    int mx = x + dx[i], my = y + dy[i];
                    if (mx >= 0 && mx < image.Length && my >= 0 && my < image[0].Length)
                    {
                        DFS(image, mx, my, color, newColor);
                    }
                }
            }
        }
    }
}
